package leetcode_1000;

/**
 * @author 周杨
 * 2018年11月18日 上午11:40:15 将一个数组划分成两个子数组 左边数组里所有元素小于等于右边所有元素
 * PartitionArrayIntoDisjointIntervals_915.java
 * description:用辅助数组标记左数组最大值和右数组最大值 AC 54%
 */
public class PartitionArrayIntoDisjointIntervals_915 {
	public int partitionDisjoint(int[] A) {
        int left[]=new int[A.length];
        left[0]=A[0];
        for(int i=1;i<A.length;++i) {
        	left[i]=Math.max(left[i-1],A[i]);//保留当前左边所有最大值
        }
        int right[]=new int[A.length];
        right[A.length-1]=A[A.length-1];
        for(int i=A.length-2;i>=0;--i)
        	right[i]=Math.min(right[i+1], A[i]);
        for(int i=0;i<A.length-1;++i) {
        	if(left[i]<=right[i+1])
        		return i+1;
        }
        throw null;
    }
}
